• bruteforce 暴力破解法：窮舉所有可能，將該數除以比他小的每個正整數，如果有能被他整除的就不是質數
• Eratosthenes方法：數字由小到大，確認是質數後，將其所有倍數刪除，最後留下來的必定是質數
  Hint：若為合數，那麼它的最小質因數必定小於等於它的平方根！

def bruteforce(n):
	if n<=2:
		return 0
	else:
		prime=[]
	for i in range(2,n):
		k=0 # 質數標誌，0為質數
		for j in range(2,i):
			if i%j ==0:
				k=1
		if k==0:
			prime.append(i)
	return prime
    
def eratosthenes(n):
	isPrime = [True]*(n+1)
	isPrime[1] = False
	for i in range(2, int(n** 0.5) + 1):# 只需要做到根號n就可以完成了
		if  isPrime[i]: 
            # if isPrime[i] is True, thast is, i is prime value
			for j in range(i*i, n+1, i): # 如果i是質數，則篩掉它的倍數
				isPrime[j] = False
	return [x for x in range(2,n+1) if isPrime[x]]

if __name__ == "__main__":
    print(bruteforce(120))
	print(eratosthenes(120))
#output:[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]